<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3480：[Usaco2014 Mar]Mooo</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2014 Mar]Mooo</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2014 Mar]Mooo</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2014 Mar]Mooo                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">Farmer John has completely forgotten how many cows he owns! He is too embarrassed to go to his fields to count the cows, since he doesn't want the cows to realize his mental lapse. Instead, he decides to count his cows secretly by planting microphones in the fields in which his cows tend to gather, figuring that he can determine the number of cows from the total volume of all the mooing he hears. FJ's N fields (1 &lt;= N &lt;= 100) are all arranged in a line along a long straight road. Each field might contain several types of cows; FJ owns cows that come from B different breeds (1 &lt;= B &lt;= 20), and a cow of breed i moos at a volume of V(i) (1 &lt;= V(i) &lt;= 100). Moreover, there is a strong wind blowing down the road, which carries the sound of mooing in one direction from left to right: if the volume of mooing in some field is X, then in the next field this will contribute X-1 to the total mooing volume (and X-2 in the field after that, etc.). Otherwise stated, the mooing volume in a field is the sum of the contribution due to cows in that field, plus X-1, where X is the total mooing volume in the preceding field. Given the volume of mooing that FJ records in each field, please compute the minimum possible number of cows FJ might own. The volume FJ records in any field is at most 100,000. </span></p>
<p>J有n块田，在一条直线上，田里有b种牛，每种牛的都有自己的叫声大小vi，由于有风，每块田可以听到的叫声大小为田里所有牛的叫声和加左边的叫声大小减一(最左边那块田的话，则只能听到自己田地里的声音），给定每种牛的叫声大小已及每块田所听到的声音，求最小可能存在多少头牛，没有解输出-1</p></p><hr/><h3>输入格式</h3><p><p><font size="4">* Line 1: The integers N and B. </font></p>
<p><font size="4">* Lines 2..1+B: Line i+1 contains the integer V(i).</font></p>
<p><font size="4"> * Lines 2+B..1+B+N: Line 1+B+i contains the total volume of all mooing in field i. </font></p></p><hr/><h3>输出格式</h3><p><p><font size="4">&nbsp;* Line 1: The minimum number of cows owned by FJ, or -1 if there is no configuration of cows consistent with the input.&nbsp;</font></p></p><hr/><h3>样例输入</h3><pre>5 2
5
7
0
17
16
20
19

INPUT DETAILS: FJ owns 5 fields, with mooing volumes 0,17,16,20,19.
 There are two breeds of cows; 
the first moos at a volume of 5, and the other at a volume of 7.
</pre><hr/><h3>样例输出</h3><pre> 4 
至少存在四头牛，其中有三头在第二块田地（二头第一种类的，一头第二种类的）,一头在第四块田地（其为第一种类）</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Silver</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3480" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3480" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>